package cn.edu.njust.alg.leetcode;

/**
 * 创建时间：2015年6月15日 上午11:47:37 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Leetcode_0_t.java 类说明：
 */
public class Leetcode_64_Minimum_Path_Sum {

	public static int minPathSum(int[][] grid) {
		if (grid.length == 0 || grid[0].length == 0) {
			return 0;
		}
		int i, j;
		int[][] dp = new int[grid.length][grid[0].length];
		dp[0][0] = grid[0][0];
		for (i = 1; i < grid[0].length; i++) {
			dp[0][i] = dp[0][i - 1] + grid[0][i];
		}
		for (i = 1; i < grid.length; i++) {
			dp[i][0] = dp[i - 1][0] + grid[i][0];
		}
		for (i = 1; i < grid.length; i++) {
			for (j = 1; j < grid[0].length; j++) {
				dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
			}
		}

		return dp[grid.length - 1][grid[0].length - 1];
	}

	public static void main(String[] args) {
		int[][] grid = { { 1, 2 }, { 1, 1 } };
		System.out.println(minPathSum(grid));
	}

}
